﻿;Public
Macro HashTable_HashFunc(key)
	HashFunction_#key
EndMacro
Macro HashTable_Interface(key, value)
	HashTable_Interface_#key#_#value
EndMacro
Macro HashTable_Create(K, V)
	HashTable_#K#_#V#_Create
EndMacro

;Private structures
Macro HashTable_PairStruct(key, value)
	HashTable_KeyValuePair_#key#value
EndMacro
Macro HashTable_Struct(key, value)
	HashTable_Structure_#key#_#value
EndMacro
Macro HashTable_BucketStruct(key, value)
	HashTable_#key#_#value#_Bucket
EndMacro



;Private methods (static)
Macro HashTable_Insert(K, V)
	HashTable_#K#_#V#_InsertItem
EndMacro
Macro HashTable_Find(K, V)
	HashTable_#K#_#V#_GetItem
EndMacro
Macro HashTable_Remove(K, V)
	HashTable_#K#_#V#_RemoveItem
EndMacro

;Template <class T>
Macro DefineHashTable(K, V)
	;Types
	Structure HashTable_PairStruct(K, V)
		key.k
		value.v
	EndStructure
	Structure HashTable_BucketStruct(K, V)
		List Elements.HashTable_PairStruct(K, V)()
	EndStructure
	Structure HashTable_Struct(K, V)_VT
		func.l[3]
	EndStructure
	Structure HashTable_Struct(K, V)
		*VT.HashTable_Struct(K, V)_VT
		Array Buckets.HashTable_BucketStruct(K, V)(0)
	EndStructure	
	Interface HashTable_Interface(K, V)
		Insert.b(key.K, *value.V)
		Find.l(key.K)
		Remove.b(key.K)
	EndInterface
	
	Procedure.l HashTable_#K#_#V#_GetItemFromBucket(*table.HashTable_Struct(K,V), key.K, bucket.l)
		ForEach *table\Buckets(bucket)\Elements()
			If *table\Buckets(bucket)\Elements()\key = key
				ProcedureReturn @*table\Buckets(bucket)\Elements()\value
			EndIf
		Next
		
		ProcedureReturn 0
	EndProcedure
	
	Procedure.l HashTable_Find(K, V)(*table.HashTable_Struct(K,V), key.K)
		Protected bucket = HashTable_HashFunc(K)(key, ArraySize(*table\Buckets()))
		
		ProcedureReturn HashTable_#K#_#V#_GetItemFromBucket(*table, key, bucket)
	EndProcedure
	
	Procedure.b HashTable_Insert(K, V)(*table.HashTable_Struct(K,V), key.K, *value.V)
		Protected bucket = HashTable_HashFunc(K)(key, ArraySize(*table\Buckets()))
		Protected *existingItem.V = HashTable_#K#_#V#_GetItemFromBucket(*table, key, bucket)
		
		If *existingItem = 0 ;Not found?
			AddElement(*table\Buckets(bucket)\Elements())
			
			*table\Buckets(bucket)\Elements()\key = key
			*existingItem = @*table\Buckets(bucket)\Elements()\value
		EndIf
		
		CopyStructure(*value, *existingItem, V)
		ProcedureReturn #True
	EndProcedure
	
	Procedure.b HashTable_Remove(K, V)(*table.HashTable_Struct(K,V), key.K)
		Protected bucket = HashTable_HashFunc(K)(key, ArraySize(*table\Buckets()))
		
		ForEach *table\Buckets(bucket)\Elements()
			If *table\Buckets(bucket)\Elements()\key = key
				DeleteElement(*table\Buckets(bucket)\Elements())
				ProcedureReturn #True
			EndIf
		Next
		
		ProcedureReturn #False
	EndProcedure
	
	Procedure HashTable_Create(K, V)(size.l)
		Protected *result.HashTable_Struct(K,V) = AllocateMemory(SizeOf(HashTable_Struct(K,V)))
		Dim *result\Buckets(size)
		
		*result\VT = AllocateMemory(SizeOf(HashTable_Struct(K, V)_VT))
		*result\VT\func[0] = @HashTable_Insert(K, V)()
		*result\VT\func[1] = @HashTable_Find(K, V)()
		*result\VT\func[2] = @HashTable_Remove(K, V)()
		
		ProcedureReturn *result
	EndProcedure
	
EndMacro



;test
Procedure.f Fract(value.f)
	ProcedureReturn value - Round(value, #PB_Round_Down)
EndProcedure
Procedure.l HashTable_HashFunc(l)(key.l, tablesize) 
	ProcedureReturn tablesize * Fract(0.6180339887 * key)
EndProcedure


EnableExplicit
DefineHashTable(l, string)
DisableExplicit

	
*ht.HashTable_Interface(l,string) = HashTable_Create(l,string)(512)
	
str.string\s = "trololo"
*ht\Insert(100, @str)
str.string\s = "ololololo-eee"
*ht\Insert(102, @str)

*s.string = *ht\Find(101)
If *s = 0 : Debug "Not found" : Else : Debug *s\s : EndIf
*s.string = *ht\Find(102)
If *s = 0 : Debug "Not found" : Else : Debug *s\s : EndIf
*s.string = *ht\Find(100)
If *s = 0 : Debug "Not found" : Else : Debug *s\s : EndIf



; IDE Options = PureBasic 5.11 (Windows - x86)
; CursorPosition = 24
; Folding = ---
; EnableXP